package lib;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author Igor Covganet
 * @Created March 06, 2011
 * 
 * The methods in this class are tested and work well.
 */
public class MaxBipartiteMatching {
	public int[] lefts = null, rights = null;

	/**
	 * Basically assignment problem.
	 * Should find the maximum match, where matches[i][j] is the profit from connecting i with j.
	 * Up to 450 nodes in 1 second.
	 */
	public void maxMatch(int[][] matches) {
		// check the symmetry
		if(matches.length != matches[0].length) {
			int[][] nm = new int[Math.max(matches.length, matches[0].length)][];
			for(int i = 0; i < nm.length; i++) {
				if(i < matches.length && matches[0].length > matches.length) {
					nm[i] = matches[i];
				} else {
					nm[i] = new int[nm.length];
					if(i < matches.length) {
						System.arraycopy(matches[i], 0, nm[i], 0, matches[i].length);
					}
				}
			}
			maxMatchContinue(nm);
		} else {
			maxMatchContinue(matches);
		}
	}
	
	/**
	 * Basically assignment problem.
	 * Should find the maximum match, where matches[i][j] is the profit from connecting i with j.
	 * The inexistent nodes should be filled with zero, or some negative value.
	 * There has to be the same number of nodes in left and right. If it's not initially, add some empty nodes before calling this function.
	 * In result lefts[i] will denote the index of node that should be connected with i.
	 */
	public void maxMatchContinue(int[][] matches) {
		int size = matches.length;
		int[] lx = new int[size];
		int[] ly = new int[size];
		// create initial weights for nodes.
		for(int i = 0; i < size; i++) {
			int max = 0;
			for(int j = 0; j < size; j++) {
				max = Math.max(max, matches[i][j]);
			}
			lx[i] = max;
		}
		// create M - the bipartite graph with matching lx[i] + ly[j] = matches[i][j].
		boolean[][] perfectMatch = new boolean[size][size];
		for(int i = 0; i < perfectMatch.length; i++) {
			for(int j = 0; j < perfectMatch.length; j++) {
				if(lx[i] + ly[j] == matches[i][j]) {
					perfectMatch[i][j] = true;
				}
			}
		}
		// make the initial match
		bestMatch(perfectMatch);
		// variables to store S and T values
		boolean[] inT = new boolean[size];
		int[] sVals = new int[size], tVals = new int[size];
		int sInd = 0, tInd = 0;
		LinkedList<Integer> queue = new LinkedList<Integer>();
		// every node from right will be invited in T set by some node in left.
		// invitedBy[rightNode] = leftNode
		// if augmenting path is found, we take the free right node found (the last)
		// and get its invitation, left node matching with it.
		// the next right node to be matched becomes the node right[left].
		// we do this until we match some right node with the invitation sent by initial free left node.
		int[] invitedBy = new int[size];
		boolean isOk = false;
		boolean foundAugmentingPath = true;
		while(!isOk) {
			// check if it's perfect
			if(foundAugmentingPath) {
				isOk = true;
				for(int i = 0; i < size; i++) {
					if(lefts[i] == -1) {
						Arrays.fill(inT, false);
						queue.clear();
						isOk = false;
						sVals[0] = i;
						sInd = 1;
						tInd = 0;
						queue.add(i);
						isOk = false;
						break;
					}
				}
				if(isOk) {
					return;
				}
			}
			// fill S and T
			foundAugmentingPath = false;
			while(queue.size() > 0 && !foundAugmentingPath) {
				int val = queue.removeFirst();
				for(int i = 0; i < size && !foundAugmentingPath; i++) {
					if(perfectMatch[val][i] && !inT[i]) {
						if(rights[i] != -1) {
							queue.add(rights[i]);
							inT[i] = true;
							invitedBy[i] = val;
							sVals[sInd] = rights[i];
							tVals[tInd] = i;
							sInd++;
							tInd++;
						} else {
							// found an augmenting path
							foundAugmentingPath = true;
							int lastLeft = val, lastRight = i;
							while(lastLeft != sVals[0]) {
								int tmpRight = lefts[lastLeft];
								lefts[lastLeft] = lastRight;
								rights[lastRight] = lastLeft;
								lastRight = tmpRight;
								lastLeft = invitedBy[lastRight];
							}
							lefts[lastLeft] = lastRight;
							rights[lastRight] = lastLeft;
							break;
						}
					}
				}
			}
			if(foundAugmentingPath) {
				continue;
			}
			// enlarge the set of matchings by changing lx and ly
			int minDif = Integer.MAX_VALUE, bestInS = -1, bestInY = -1;
			for(int i = 0; i < sInd; i++) {
				for(int j = 0; j < size; j++) {
					if(inT[j]) {
						continue;
					}
					if(lx[sVals[i]] + ly[j] - matches[sVals[i]][j] < minDif) {
						minDif = lx[sVals[i]] + ly[j] - matches[sVals[i]][j];
						bestInS = sVals[i];
						bestInY = j;
					}
				}
			}
			for(int i = 0; i < sInd; i++) {
				lx[sVals[i]] -= minDif;
				queue.add(sVals[i]);
			}
			for(int i = 0; i < tInd; i++) {
				ly[tVals[i]] += minDif;
				for(int j = 0; j < lx.length; j++) {
					if(perfectMatch[j][tVals[i]] && lx[j] + ly[tVals[i]] > matches[j][tVals[i]]) {
						perfectMatch[j][tVals[i]] = false;
					}
				}
			}
			perfectMatch[bestInS][bestInY] = true;
		}
	}
	
	/** The matched nodes from left will have the index of node from right. The non-matched nodes will have the value -1 assigned. */
	private void bestMatch(boolean[][] matches) {
		int m = matches.length;
		int n = m > 0 ? matches[0].length : 0;
		
		lefts = new int[m];
		rights = new int[n];
		
		Arrays.fill(lefts, -1);
		Arrays.fill(rights, -1);
		// make the initial match
		for (int i = 0; i < lefts.length; i++) {
			for (int j = 0; j < rights.length; j++) {
				if(rights[j] >= 0 || !matches[i][j]) {
					continue;
				}
				
				lefts[i] = j;
				rights[j] = i;
				break;
			}
		}
		
		// find augmenting path
		boolean vb = true;
		while(vb) {
			vb = false;
			
			for(int i = 0; i < lefts.length; i++) {
				if(lefts[i] >= 0) {
					continue;
				}
				
				boolean[] used = new boolean[lefts.length];
				used[i] = true;
				LinkedList<LinkedList<Integer>> q = new LinkedList<LinkedList<Integer>>();
				for(int j = 0; j < rights.length; j++) {
					if(matches[i][j]) {
						LinkedList<Integer> list = new LinkedList<Integer>();
						list.add(j);
						q.add(list);
						used[rights[j]] = true;
					}
				}
				
				while(q.size() > 0 && !vb) {
					LinkedList<Integer> path = q.removeFirst();
					int val = rights[path.getLast()];
					for(int j = 0; j < rights.length; j++) {
						if(matches[val][j]) {
							if(rights[j] == -1) {
								// augmenting path found!!
								int last = path.removeFirst();
								lefts[i] = last;
								for(int y : path) {
									lefts[rights[last]] = y;
									last = y;
								}
								lefts[val] = j;
								for(int k = 0; k < m; k++) {
									if(lefts[k] != -1) {
										rights[lefts[k]] = k;
									}
								}
								vb = true;
								break;
							} else if(!used[rights[j]]) {
								LinkedList<Integer> tmp = new LinkedList<Integer>();
								for(int y : path) {
									tmp.add(y);
								}
								tmp.add(j);
								q.add(tmp);
								used[rights[j]] = true;
							}
						}
					}
				}
			}
		}
	}
}
